强化学习

2.1 强化学习

2.1.1 强化学习的基本原理

强化学习的原理
- $s_t$ $r_t$ $a_t$ .（这里不研究与之前状态有关的情况）
  智能体又称为 RL agent，即 Reinforcement Learning agent.
- $s_t$ $a_t$ $s_{t+1}$ $r_{t+1}$ .
- 该过程循环进行，直到抵达终止条件.
- 强化学习的模型是马尔科夫决策过程.
- 我们将学习强化学习中三类常见的算法：动态规划、时序差分、蒙特卡洛.
智能体的组成
- 策略
  - $\pi$ 是一个策略 (Policy).
  - $\pi(s)$ $s$ 下可能发生的行为, 是一个随机变量.
  - $\pi(a \mid s) = P(A_t = a \mid S_t = s)$ .
- 值函数
  - $t$ $S_t$ $R_t$ .
  - $G_t = \dsum_{k=0}^\infty \gamma^k R_{t + k + 1}$ , 又称为长期回报.
  - $V_\pi(s) = E_\pi\bqty{G_t \mid S_t = s}$ .
  - $Q_\pi(s, a) = E_\pi\bqty{G_t \mid S_t = s, A_t = a}$ .
- 模型
  - $P_{ij}^\pi = P\Bqty{S_{t + 1} = s' \mid S_t = s}$ .
  - $P_{ij}^a = P\Bqty{S_{t + 1} = s' \mid S_t = s, A_t = a}$ .
  - $R_s^\pi = E\bqty{R_{t + 1} \mid S_t = s}$ .
  - $R_s^a = E\bqty{R_{t+1} \mid S_t = s, A_t = a}$ .

2.1.2 强化学习的三对概念

学习与规划
- 学习：智能体通过与环境交互的过程，以此估计环境模型的参数，或者调整智能体行为.
- 规划：根据学习得到的数据，优化智能体的策略，从而得到最大的回报的过程.
探索与利用
- 利用：根据采取样本的信息，选取当下局部最优的行为.
- 探索：不仅仅采取当下最优的行为，而是探索新的行为，以期得到全局最优的行为.
预测与控制
- 预测：评估当前策略，即计算或估计状态值函数或行为值函数.
- 控制：根据对当前策略评估而得到的值函数，对策略进行优化.

2.1.3 强化学习的具体分类（略）

这部分可略去不看.

机器学习 (属于人工智能)
- 分类一
  - 监督学习
    - 有标记的数据.
    - 预测未知数据的标记.
    - 静态数据.
  - 非监督学习
    - 无标记的数据.
    - 挖掘数据潜在结构.
    - 静态数据.
  - 强化学习
    - 没有标记, 只有一个延迟的回报信号.
    - 属于序贯决策 (Sequential Decision Making) 模型.
    - 数据通过与环境不断交互而产生, 即动态数据.
    - 数据之间高度相关.
- 分类二
  - 传统的机器学习: 需要人工提取特征.
  - 深度学习: 无需人工提取特征 (属于监督学习).
  - 强化学习: 目的是在环境中最大化奖励.
  - 深度强化学习: 结合深度学习与强化学习.
强化学习
- 分类一
  - 有模型方法: 如动态规划法.
  - 无模型方法: 如蒙特卡洛法、时序差分法.
- 分类二
  - 基于值函数的方法 (Value Based)
  - 基于策略的方法 (Policy Based)
  - 行动者-评论家方法 (Actor-Critic)

2.2 动态规划

2.2.1 思路介绍

我们想要求解强化学习模型（即马尔科夫决策过程）的最优策略，可以循环进行策略评估与策略提升：

策略评估（预测）：计算当前策略的状态值函数或行为值函数.
策略提升（控制）：根据当前策略的值函数去优化策略.

反复进行上述过程，直到策略稳定为最优策略. 该思路称为广义策略迭代.

动态规划、蒙特卡洛、时序差分，都属于广义策略迭代，其中动态规划需要知道模型的参数（如回报函数与状态转移概率矩阵），蒙特卡洛与时序差分则无需模型参数.

动态规划（DP，dynamic planning）分为策略迭代和价值迭代两种算法.

2.2.2 策略迭代

1 策略评估

在马尔科夫决策过程中，我们得到了贝尔曼期望方程，

\begin{aligned} v_{π} (s) & = \sum_{a \in A} π (a ∣ s) (R_{s}^{a} + γ \sum_{s^{'} \in S} P_{s s^{'}}^{a} v_{π} (s^{'})), \\ q_{π} (s, a) & = R_{s}^{a} + γ \sum_{s^{'} \in S} P_{s s^{'}}^{a} \sum_{a^{'} \in A} π (a^{'} ∣ s^{'}) q_{π} (s^{'}, a^{'}) . \end{aligned}

我们可以直接联立方程去求解，但是这样做计算量很大，实际应用不便.

另一种思路是，利用上述方程自举求得近似值，逐渐逼近精确值：

\begin{aligned} v_{π}^{(k + 1)} (s) & = \sum_{a \in A} π (a ∣ s) (R_{s}^{a} + γ \sum_{s^{'} \in S} P_{s s^{'}}^{a} v_{π}^{(k)} (s^{'})), \\ q_{π}^{(k + 1)} (s, a) & = R_{s}^{a} + γ \sum_{s^{'} \in S} P_{s s^{'}}^{a} \sum_{a^{'} \in A} π (a^{'} ∣ s^{'}) q_{π}^{(k)} (s^{'}, a^{'}) . \end{aligned}

实际应用中只需求解行为值函数. 如果采取任一行为后状态的转移是确定的, 而非随机的, 则可以不求解行为值函数, 而转为求解状态值函数.

2 策略改进

$\pi_n$ $\pi_{n+1}(s) \in \argmax a Q_{\pi_n}(s, a)$ .

2.2.3 价值迭代

1 算法介绍

利用贝尔曼最优方程自举,

V_{k + 1} (s) = max_{a \in A} (R_{s}^{a} + γ \sum_{s^{'} \in S} P_{s s^{'}}^{a} V_{k} (s^{'})),

求出最优值函数后, 贪心策略即为最优策略.

2 算法优势

策略迭代中，每次迭代都要通过自举进行策略评估；而价值迭代，只需要自举求得最优值函数. 因此一般来说，价值迭代的计算量更小.

2.3 蒙特卡洛

2.3.1 蒙特卡洛思路介绍

动态规划在策略评估时，需要知道模型的全部参数（状态转移概率矩阵与回报函数），但实际情景中不一定可知，即使可知，也可能十分复杂. 因此我们通过采样数据去估计值函数，该思路称为蒙特卡洛方法（MC，Monte-Carlo）.

2.3.2 在线策略蒙特卡洛

1 蒙特卡洛评估

采样得到轨迹
- $\aqty{s_0, a_0, r_1, \cdots, s_T, a_T, r_T}$ .（直接得到的数据，不便于使用）
- $\aqty{s_0, a_0, G_1, \cdots, s_T, a_T, G_T}$ .（由立即回报计算而得，便于使用）
计算平均回报
- $s$ 时的累积回报.（可能会有偏差）
- $s$ 时的累积回报.（无偏估计）
增量式公式
- $k$ $V_{k+1}(s_t)$ .
- $k + 1$ $G_t$ 后的值函数为
  $\begin{aligned} V_{k + 1} (s_{t}) & \leftarrow \frac{k V_{k} (s_{t}) + G_{t}}{k + 1} = V_{k} (s_{t}) + \frac{G_{t} - V_{k} (s_{t})}{k + 1} . \end{aligned}$
修正后的更新公式
- $\dfrac{1}{k+1}$ $\alpha \in (0, 1)$ .
- $\alpha$ $k$ $\alpha$ 越大, 代表越靠后的累积回报越重要.
  $V (s_{t}) \to V (s_{t}) + α (G_{t} - V (s_{t})) .$
若要估计行为值函数，则类似可得
$Q (s_{t}, a_{t}) \leftarrow Q (s_{t}, a_{t}) + α (G_{t} - Q (s_{t}, a_{t})) .$

2 蒙特卡洛控制

$\ve$ -贪心探索，即

$\ve$ 从所有行为中均匀随机选取一个.
$1 - \ve$ 的概率选取当前最优行为.

$m$ 个行为, 有且仅有一个最优行为, 那么

$1 - \dfrac{m-1}{m} \ve$ .
$\dfrac{\ve}{m}$ .

3 在线/离线策略

首先引入概念：

$s$ $s$ 时使用的策略就是行为策略.
$s$ 之后，不断采取行为、转移状态、最终获取整体回报的过程中使用的策略就是原始策略.

$\ve$ -贪心策略，称为 在线策略蒙特卡洛.

$\ve$ -贪心策略获取更丰富的采样数据，通过贪心策略得到整体回报，那么最终我们得到的策略（贪心策略）就是确定性的了.

像这样在线策略与原始策略不同的蒙特卡洛方法，称为 离线策略蒙特卡洛，也就是下一小节中所要探讨的.

2.3.3 离线策略蒙特卡洛（略）

可以跳过本节不看.

$\pi'$ $\ve$ -贪心策略或随机策略.
$\pi$ $\ve$ -贪心策略 (如贪心策略).

1 重要性采样方法

前置知识
- $E\bqty{X} = E\bqty{E\bqty{X \mid Y}}$ .
- $E\bqty{f(x)} = \dint_x p(x) f(x) \dx = \dint_x q(x) \dfrac{p(x)}{q(x)} f(x) \dx$ .
- $\hat E\bqty{f(x)} = \dfrac{1}{m} \dsum_{i=1}^m f(x_i) = \dfrac{1}{m} \dsum_{i=1}^m \dfrac{p(x'_i)}{q(x'_i)} f(x'_i)$ .
- 随机采样, 可得期望的无偏估计.
行为值函数
- $\pi'$ $Q(s, a) = \dfrac{1}{m} \dsum_{i = 1}^m \dfrac{P_i^\pi}{P_i^{\pi'}} G_i$ .
- 重要采样比率 $\rho_i^T = \dfrac{P_i^\pi}{P_i^{\pi'}} = \d\prod_{j=0}^{T-1} \dfrac{\pi(a_j \mid s_j)}{\pi'(a_j \mid s_j)}$ .
- $Q(s_t, a_t) \la Q(s_t, a_t) + \alpha(\rho_i^T G_t - Q(s_t, a_t))$ .

2 加权重要性采样

为减小方差,

\begin{aligned} \hat{E} [f (x)] & = \frac{\sum_{i = 1}^{m} \frac{p (x_{i}^{'})}{q (x_{i}^{'})} f (x_{i}^{'})}{\sum_{i = 1}^{m} \frac{p (x_{i}^{'})}{q (x_{i}^{'})}}, Q (s, a) = \frac{\sum_{i = 1}^{m} ρ_{i}^{T} G_{i}}{\sum_{i = 1}^{m} ρ_{i}^{T}}, \\ Q_{m} (s, a) & = \frac{ρ_{m}^{T} G_{m} + Q_{m - 1} (s, a) \sum_{i = 1}^{m - 1} ρ_{i}^{T}}{\sum_{i = 1}^{m} ρ_{i}^{T}} \\ = Q_{m - 1} (s, a) + \frac{ρ_{m}^{T}}{\sum_{i = 1}^{m} ρ_{i}^{T}} (G_{m} - Q_{m - 1} (s, a)) . \end{aligned}

2.4 时序差分

2.4.1 时序差分思路介绍

1 时序差分简介

$G_t$ $V_\pi(S_t) = E_\pi\bqty{G_t \mid S_t = s}$ .

$V_\pi(S_t) = E_\pi\bqty{ R_{t + 1} + \gamma V(S_{t + 1}) \mid S_t = s }$ $V_\pi(S_t)$ $G_t$ $R_{t+1} + \gamma V(S_{t+1})$ 的期望，因此我们可以采样算出其均值，以估计值函数.

这么做的好处是，只需要一部分的轨迹，从而缩短了采样的时间，从而更快地估计值函数.

$G_t$ $R_{t + 1} + \gamma V(S_{t + 1})$ TD 目标值 $\delta_t = R_{t + 1} + \gamma V(S_{t + 1}) - V(s_t)$ 称为 TD 误差.

时序差分与蒙特卡洛都是无模型方法，同样分为在线策略（如 Sarsa）与离线策略（如 Q-Learning）两种.

2 三种算法对比（略）

动态规划 (DP, Dynamic Programming)
- $V_\pi(S_t) = E_\pi\bqty{R_{t + 1} + \gamma V(S_{t+1}) \mid S_t = s}$ .
- 一步预测, 自举. 无需采样, 需要完整模型.
- 无偏差, 无方差.
- 有模型方法, 具有马尔科夫性.
蒙特卡洛 (MC, Monte Carlo)
- $V_\pi(S_t) \approx G_t \mid S_t = s$ .
- 不自举. 依靠采样, 学习完整的轨迹.
- 无偏估计, 方差较大.
- 无模型方法, 无马尔科夫性.
时序差分 (TD, Temporal Difference)
- $V_\pi(S_t) \approx R_{t + 1} + \gamma V(S_{t + 1}) \mid S_t = s$ .
- 一步预测, 自举. 需要采样, 学习部分轨迹.
- 右偏估计, 方差较小.
- 无模型方法, 无马尔可夫性.

三种算法都遵循广义策略迭代框架.

2.4.2 在线策略时序差分：Sarsa

Q (S, A) \leftarrow Q (S, A) + α (R + γ Q (S^{'}, A^{'}) - Q (S, A)) .

$A$ $A'$ 由目标策略得到.

$\ve$ -贪心策略.

2.4.3 离线策略时序差分：Q-Learning

1 离线策略 TD（略）

离线策略 TD
- $\mu(a \mid s)$ 进行数据采样.
- $\pi(a, s)$ .
TD 目标
- $\pi$ $\pi$ $R_{t + 1} + \gamma Q(s_{t + 1}, a_{t + 1})$ .
- $\mu$ $\pi$ $\dfrac{\pi(a_t \mid s_t)}{\mu(a_t \mid s_t)} \pqty{R_{t + 1} + \gamma Q(s_{t + 1}, a_{t + 1})}$ .
离线策略 TD 方法的更新公式
$Q (s_{t}, a_{t}) \leftarrow Q (s_{t}, a_{t}) + α (\frac{π (a_{t} ∣ s_{t})}{μ (a_{t} ∣ s_{t})} (R_{t + 1} + γ Q (s_{t + 1}, a_{t + 1})) - Q (s_{t}, a_{t})) .$

2 Q-learning

Q (S_{t}, A_{t}) \leftarrow Q (S_{t}, A_{t}) + α (R_{t + 1} + γ Q (S_{t + 1}, A^{'}) - Q (S_{t}, A_{t})) .

$A_t$ $\mu$ $\ve$ -贪心策略).
$A'$ $\pi$ (贪心策略) 产生, 即
$A^{'} = π (S_{t + 1}) = \underset{a^{'}}{argmax} Q (S_{t + 1}, a^{'}),$
$R_{t + 1} + \gamma \max_{a'} Q(S_{t + 1}, a')$ , 上式变为
$Q (S_{t}, A_{t}) \leftarrow Q (S_{t}, A_{t}) + α (R_{t + 1} + γ max_{a^{'}} Q (S_{t + 1}, a^{'}) - Q (S_{t}, A_{t})) .$
备注：一般来说，离线策略产生的轨迹数据更为丰富，且获得的结果是确定性策略，因此比较常用.